In many environments data in various forms (e.g., various protocols, modulations, etc.) can be transmitted over a channel from a transmitter to a receiver. Depending on the type and circumstances of operation, some channels are more or less prone or susceptible to loss or degradation of the data being transmitted over the channel, with differing channels having differing degrees of potential loss or corruption. For example, a wireline channel typically has a relatively higher degree of integrity and reliability than a channel existing over a radio or interface.
Detection of loss or inaccurate transmission of data over a channel is possible when certain additional information in the form of an error detection code is added to the data stream. For example, at a transmitter a frame or block of data can have appended to it an error detection code in the form of (for example) a check character(s) or check sum which is computed or otherwise derived from the block. Upon reception of the block by the receiver, the receiver can independently recompute or re-derive the error detection code (e.g., the receiver's version of the check character(s) or check sum). If the recomputed or re-derived error detection code (e.g., check sum) is the same as the error detection code included in the received block or frame, the receiver can confirm that the block or frame is correctly decoded.
In addition to error detection techniques, error correcting techniques are also known. For example, error correction codes (generated by polynomials that operate over a frame or block of user data) can also be added to the data stream. Upon reception of the complete frame or block, using the known error correction code/technique the receiver can locate and correct certain errors in the data stream.
Thus, error control coding is used in many communication applications to introduce redundancy into the transmitted information sequence so that the decoder at the receiver may recover from errors induced during transmission. Error control codes may broadly be classified as block codes and convolutional codes. The encoding operation for a (n, k) linear block code may be characterized as v=GT u, where u is a k×1 vector of representing the information sequence, G is a k×n generator matrix that defines the code and v is a n×1 vector representing the encoded sequence.
Convolutional codes may also be represented as described above, although their encoding operation may be implemented in a simple manner. Convolutional codes are commonly specified by three parameters; (n, m, q). Of these three parameters, n represents the number of output bits; m represents the number of input bits; and q represents the number of memory registers employed to implement the convolutional code. The quantity m/n, called the code rate, is a measure of the efficiency of the code. Often the manufacturers of convolutional code chips specify the code by parameters (n,m,k), where k is the constraint length k=m(q−1).
Convolutional codes convolve the input sequence with one or more generators with the encoding operation being implemented quite simply using shift registers. FIG. 1 shows an example encoder and encoding operation for a convolutional code having a code rate of 1/2. The information sequence u is input into the memory registers (e.g., shift registers) M1 and M2 and is input one bit at each clock time. The convolutional coder also include n number of modulo-2 adders which represent the n number of encoded bits which are output each clock time. FIG. 1 thus shows two adders A1 and A2 since n is two for the case shown in FIG. 1. The memory registers M1 and M2 are connected to the adders A1 and A2 in accordance with the particular generator polynomials chosen for the convolutional encoder. That is, which of the memory registers is connected to each adder depends on the generator polynomials chosen for the coder. One code can have completely different properties from another one depending on the particular generator polynomials chosen.
An encoder structure of a rate 1/n feedforward convolutional code (CC) with overall constraint length v is shown in FIG. 2, where the content consisting of zeros and ones of the v number of shift-register elements is called the state of the encoder. The n number of generator polynomials specify the connections from the shift-registers to the n outputs. The n number of generator polynomials are represented by the set G=(g0, . . . , gn-1), where g0=(g0(0), g0(1), . . . , g0(v)), . . . , gn-1=(gn-1(0), gn-1(1)s, . . . , gn-1(v)). The coefficients gk(j), for k=0, . . . , n−1 and j=0, . . . , v, is either 0 (no connection) or 1 (with connection). Ui is the input bit at time i, and (vi(0), . . . , vi(n−1)) are the n output bits at time i. Thus, a convolutional code can be specified by its set of generator polynomials G=(g0, . . . , gn-1).
Another example encoder, which happens to implement a Tail-biting convolutional codes (TBCC) [hereinafter discussed], is shown in FIG. 2. The encoder of FIG. 2 has code rate 1/n=1/2, constraint length v=6, and G=(g0,g1), where g0=(1, 1, 1, 1, 0, 0, 1) and g1=(1, 0, 1, 1, 0, 1, 1). In other words, the adder Ag0 for the first polynomial g0 is connected to receive the bit values from the first through fourth positions and the seventh position of the shift register chain of FIG. 2 (e.g., the first position being the input to shift register Ui-1; the second position being the output of shift register Ui-2; the third position being the output of shift register Ui-3; and so on to the seventh position being the output of shift register Ui-6). The adder Ag1 for the second polynomial g1 is connected to receive the bit values from the first, third, fourth, sixth, and seventh positions of the shift register chain of FIG. 2.
To represent the generator polynomials in a more compact way, an octal notation is usually used, where zeros (0) are appended on the right of the binary notation to make the total number of digits a multiple of 3. For example, with reference to the encoder of FIG. 2, two zeroes are appended to the right of g0 to generate the binary vector g0′=(1, 1, 1, 1, 0, 0, 1, 0, 0). Then the digits in g0′ are grouped with three digits per group and the result is g0″=(111, 100, 100). Finally each group in g0″ is transformed to its equivalent octal notation and the result is (7, 4, 4). The generator polynomials depicted for the encoder of FIG. 2 in octal notation are thus given by G=(744, 554). The more compact octal notation is typically used herein to represent the generator polynomials.
In the recursive convolutional encoder of FIG. 3 the sequence of input bits dn is fed to shift registers Rn-1 through Rn-k. The contents of the shift registers R are applied to gates whose outputs are determined by coefficients al through ak of the feedback generator polynomial of the encoder. The contents of the shift registers R are also applied to other gates whose outputs are determined by coefficients b1 through bk of the feedforward generator polynomial of the encoder. Typically in operation the input sequence d0 is output first, followed by the encoded output represented in FIG. 3 by sequence pn. In FIG. 3 two bits (systematic bit d0 and parity bit pn) are output for each input bit dn.
A convolutional turbo-encoder uses two component convolutional encoders with the input between the two encoders. FIG. 4 shows such a convolutional turbo-encoder with its two component convolutional encoders C1 and C2. That is, in the case of a turbo-encoder, the component encoders are typically recursive systematic encoders in contrast with the non-systematic encoder shown in FIG. 1. A recursive systematic encoder has feedback from the gates as shown in the FIG. 3, which gives it the recursive property. The term systematic refers to the fact that part of the encoder output is the information sequence itself.
Convolutional codes and turbo codes are particularly useful in scenarios where a series of different code rates must be used. In such situations, typically, a low rate “mother code” is used as the basic code from which codes for all the other higher code rates are derived. For the special case of the number of input bits (m) being 1, the codes of rates like 1/2, 1/3, 1/4, or 1/5, are sometimes called mother codes. The technique of not transmitting a selected one or more of the output bits is called puncturing, and can be used to provide a different code rate. Thus, these higher code rates are derived by puncturing the output of the encoder, i.e., by only selecting some of the output bits. The number of fraction of output bits discarded determines the new coding rate.
The output of a convolutional encoder depends on the contents of the shift registers when the first input bit is encoded. The contents are typically set to zero. The actual rate is slightly lower than the basic code rate due to the extra encoded bits that are generated when the last few bits in the information sequences are flushed out of the shift registers. These bits are called the tail of the information sequence. Thus, for the rate-1/2 code shown in FIG. 2, if a sequence of 12 information bits is encoded, the number of output bits generated is (12+6)*2=36. Thus, the actual rate in this case is 1/3, although the encoding was done using a rate 1/2 code. As the length of the information bit sequence increases, the effect of the tail on the rate diminishes. However, for short sequences the effect can be significant as evidenced by the example above.
In such situations, a tail-biting encoder is useful. Tail-biting convolutional codes (TBCC) are simple and powerful forward error correction (FEC) codes, as described, e.g., in H. H. Ma and J. K. Wolf, “On tail biting convolutional codes,” IEEE Trans. Commun., vol. 34, pp. 104-111, February 1986. Tail-biting codes are described, e.g., in U.S. patent application Ser. No. 12/140,956, entitled “REDUCED-COMPLEXITY DECODING ALGORITHMS FOR TAIL-BITING CONVOLUTIONAL CODES”, and U.S. patent application Ser. No. 12/260,340, entitled “Optimum Distance Spectrum Feedforward Tail-Biting Convolutional Codes”, both of which is incorporated by reference herein in its entirety.
In a tail-biting encoder, the initial contents of the shift register are exactly the same as the last bits in the information sequence. Thus, when encoding the sequence 101111110011 with the encoder shown in the FIG. 2, the contents of the shift register will initially be set to 110011 (from right to left in the shift registers). The encoding operation now stops without flushing out the last few bits in the information sequence from the registers since they were already in the register at the beginning. Thus, in the example above, the number of output bits produced for 12 information bits is 24 instead of 36. A tail-biting code is also a cyclic code since the codewords for circular shifts of the information sequence are the corresponding circular shifts of the encoded sequence.
Puncturing of the encoder output is widely used with both convolutional encoders and convolutional turbo encoders. In contrast to puncturing, for some block codes, a lower rate code is derived from a higher rate code by not considering some of the rows in the generator matrix. The effective code is characterized by a generator matrix that is derived from the higher code rate generator matrix by deleting these rows. Codes that are derived in this manner are called expurgated codes. Expurgated codes have been used for block codes, but to the best of the inventors' knowledge, they have not been used for convolutional codes.
Convolutional codes are widely used in many communication systems. As is known, the IEEE 802.16 Working Group on Broadband Wireless Access Standards develops formal specifications for the global deployment of broadband Wireless Metropolitan Area Networks. Although the 802.16 family of standards is officially called WirelessMAN, it has been dubbed WiMAX (from “Worldwide Interoperability for Microwave Access”) by an industry group called the WiMAX Forum. FIG. 2 shows an example encoder for the 802.16 Tail-biting convolutional codes (TBCC).
Turbo codes derived from multiple component recursive systematic convolutional codes are used in the latest generation of wireless communication standards and in numerous other applications as well. In some such applications it may be necessary to have a range of code rates where the lowest code rate is a fraction for which it is difficult to search for good codes. A range of code rates from 7/60 to 12/60 is currently being considered for the fast feedback channel (TBCC) in IEEE 802.16m.
What are needed therefore, and provided by the technology disclosed herein, are method, apparatus, and techniques for obtaining and/or using lower rate convolutional codes and convolutional turbo codes suitable from higher rate codes.